import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created by L.jp
 * Description:给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。
 * User: 86189
 * Date: 2022-07-21
 * Time: 23:55
 */
//思想：固定一个数，在数组中找两个数的和是相反数的组合，找两个数使用相对指针
public class Solution {
    public static ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> ret=new ArrayList<ArrayList<Integer>>();
        //先排序，有助于加快查找速率
        Arrays.sort(num);
        //固定一个数，要构造成三数之和，那么最多遍历到倒数第三个数
        for(int i=0;i<num.length;i++){
            //过滤掉重复的
            if(i>0 && num[i]==num[i-1]){
                continue;
            }
            //因为是排好序的，那么如果第一个数就大于0，那么肯定找不到。直接退出
            if(num[i]>0){
                break;
            }
            int left=i+1; //左指针
            int right=num.length-1; //右指针
            //相反数
            int target=-num[i];
            while (left<right){
                //左右指针之和
                int sum=num[left]+num[right];
                if(sum==target){
                    //左右指针之和等于相反数
                    ArrayList<Integer> tmp=new ArrayList<>();
                    tmp.add(num[i]);
                    tmp.add(num[left]);
                    tmp.add(num[right]);
                    ret.add(tmp);
                    //过滤掉重复的
                    while (left<right && num[left]==num[left+1]){
                        left++;
                    }
                    while (left<right && num[left]==num[right]){
                        right--;
                    }
                    //本来就是要跳过这个已经被加入的
                    left++;
                    right--;
                }else if(sum<target){
                    //看下一个数符不符合
                    left++;
                }else{
                    right--;
                }
            }
        }
        return  ret;
    }
    
    public static void main(String[] args) {
        int[] num={-10,0,10,20,-10,-40};
        System.out.println(threeSum(num));
    }
}
